package code1701_1800.code90_100;

import java.util.HashSet;

/**
 * 有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
 *
 * 给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点。
 *
 * 输入：edges = [[1,2],[2,3],[4,2]]
 * 输出：2
 * 解释：如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。
 *
 * 输入：edges = [[1,2],[5,1],[1,3],[1,4]]
 * 输出：1
 */
public class _1791findCenter {

    /**
     * 执行用时：     * 2 ms     * , 在所有 Java 提交中击败了     * 33.76%     * 的用户
     * 内存消耗：     * 63.5 MB     * , 在所有 Java 提交中击败了     * 44.51%     * 的用户
     * @param edges
     * @return
     */
    public int findCenter(int[][] edges) {
        int[] nodes = new int[edges.length+1];
        for (int i = 0; i < edges.length; i++) {
                nodes[edges[i][0]-1]++;
                nodes[edges[i][1]-1]++;
        }
        for (int i = 0; i < nodes.length; i++) {
            if(nodes[i]==edges.length){
                return i+1;
            }
        }
        return 0;
    }

    /**
     * 题解做法，因为是1-n，所以除中心节点外，其余节点都只出现了一次。所以只要找到曾经出现了的节点就直接返回。
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 63.5 MB     * , 在所有 Java 提交中击败了     * 43.67%     * 的用户
     * @param edges
     * @return
     */
    public int findCenter0(int[][] edges) {
        HashSet<Integer> set = new HashSet<>();
        for(int[] edge : edges){
            for(int node : edge){
                if(set.contains(node)) return node;
                set.add(node);
            }
        }
        return -1;
    }

}
